package com.lun.easy;

import com.lun.util.BinaryTree.TreeNode;

public class MinimumDistanceBetweenBSTNodes {
	//方法一：前后续遍历模式递归
    public int minDiffInBST(TreeNode root) {
    	int min = Integer.MAX_VALUE;
    	if(root == null) return min;
    	
    	TreeNode lp = root.left;
    	if(lp != null) {//查左子树最大值节点
    		while(lp.right != null) {
    			lp = lp.right;
    		}
    		
    		min = Math.min(min, root.val - lp.val);
    	}
    	
    	TreeNode rp = root.right;
    	if(rp != null) {//查右子树最小值节点
    		while(rp.left != null) {
    			rp = rp.left;
    		}
    		
    		min = Math.min(min, rp.val - root.val);
    	}
    	
    	min = Math.min(Math.min(min, minDiffInBST(root.left)), // 
    			minDiffInBST(root.right));
    	
        return min;
    }
    
    //方法二：中续遍历模式递归
    public int minDiffInBST2(TreeNode root) {
    	int[] min = {Integer.MAX_VALUE};
    	Integer[] prev = {null};
    	minDiffInBST2(root, min, prev);
    	return min[0];
    }
    
    private void minDiffInBST2(TreeNode node, int[] min, Integer[] prev) {
    	if(node == null) return;
    	minDiffInBST2(node.left, min, prev);
    	if(prev[0] != null)
    		min[0] = Math.min(min[0], node.val - prev[0]);
    	prev[0] = node.val;
    	minDiffInBST2(node.right, min, prev);
    }
    
}
